package com.tgy.leetcode;

import java.util.*;

/**
 *
 * https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/
 *
 *  排列有顺序，组合没顺序
 *
 *
 */

public class _1178_猜字谜 {

    public static List<Integer> findNumOfValidWords(String[] words, String[] puzzles){

        HashMap<Integer,Integer> wordsMap = new HashMap<>();

        for (String word : words) {

            int code = 0;
            char[] chars = word.toCharArray();
            for (char c : chars) {

                code |= (1 << (c - 'a'));
            }

            Integer count = wordsMap.getOrDefault(code, 0) + 1;
            wordsMap.put(code,count);
        }

        List<Integer> res = new ArrayList<>();

        for (String puzzle : puzzles) {

            int puzzleGather = 0;
            char[] chars = puzzle.toCharArray();
            for (char c : chars) {

                puzzleGather |= (1 << (c - 'a'));
            }

            int count = 0;


            int flag = (1 << (chars[0] - 'a'));
            for (int i = puzzleGather; i > 0;) {

                if ( (i & flag) != 0) {
                    count += wordsMap.getOrDefault(i,0);
                }
                i = (i - 1) & puzzleGather;
            }
            res.add(count);
        }

        return res;
    }

    public static List<Integer> findNumOfValidWords01(String[] words, String[] puzzles) {

        List<Set<Character>> puzzlesSet = new ArrayList<>();
        List<Character> firstChars = new LinkedList<>();
        for (String puzzle : puzzles) {

            Set<Character> characters = new HashSet<>();
            char[] chars = puzzle.toCharArray();
            for (char c : chars) {
                characters.add(c);
            }
            puzzlesSet.add(characters);
            firstChars.add(chars[0]);
        }

        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < puzzlesSet.size(); i++) {

            Set<Character> characters = puzzlesSet.get(i);
            Character firstChar = firstChars.get(i);
            int count = 0;
            for (String word : words) {

                boolean flag = false;
                boolean firstEqual = false;
                for (char c : word.toCharArray()) {

                    if (!characters.contains(c)) {

                        flag = true;
                        break;
                    }

                    if (firstChar.equals(c)) {

                        firstEqual = true;
                    }
                }

                if (!flag && firstEqual) {
                    count++;
                }
            }
            res.add(count);
        }

        return res;
    }

    public static void sub(int num){

//        for (int i = num; i > 0;) {
//
//            i = (i - 1) & num;
//            System.out.println(i);
//        }
        // 1010
        for (int i = num; i > 0; i--) {

            if ((i | num) == num) {
                System.out.println(i);
            }
        }
    }

    public static void main(String[] args) {

        String[] words = {"aaaa","aacct","asas","able","ability","actt","actor","access"};
        String[] puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};

        System.out.println(findNumOfValidWords(words, puzzles));
        // 1110
        sub(14);
    }

}
